package com.note.feng.leetcode.algorithms.easy;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class TwoHundredNineteen {

    /**
     * 219 存在重复元素II
     * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
     *
     * 示例 1：
     *
     * 输入：nums = [1,2,3,1], k = 3
     * 输出：true
     * 示例 2：
     *
     * 输入：nums = [1,0,1,1], k = 1
     * 输出：true
     * 示例 3：
     *
     * 输入：nums = [1,2,3,1,2,3], k = 2
     * 输出：false
     *
     * 提示：
     *
     * 1 <= nums.length <= 105
     * -109 <= nums[i] <= 109
     * 0 <= k <= 105
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/contains-duplicate-ii
     */
    /**
     *解法：哈希
     * 将值和下标存入map中，若map中包含这个值，判断当前下标与map中value的差，是否<= k,
     * 是，返回true，不是将值和下标存入map中，继续遍历
     * 若不包含这个值，将值和下标存入map
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int len = nums.length;
        if(len < 2){
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            if(map.containsKey(num)){
                int j = map.get(num);
                if(i - j <= k){
                    return true;
                }else{
                    map.put(num, i);
                }
            }else{
                map.put(num, i);
            }
        }
        return false;
    }

    /**
     *解法：滑动窗口
     * set中止保存k个元素，若set中包含这个元素，返回true
     * set长度超出k，移除第一个元素
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate2(int[] nums, int k) {
        int len = nums.length;
        if(len < 2){
            return false;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < len; i++) {
            if(!set.add(nums[i])){
               return true;
            }
            if(set.size() > k){
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}
